
//leetcode_19:删除链表倒数的第N个节点
//给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
//        进阶：你能尝试使用一趟扫描实现吗？
//        输入：head = [1,2,3,4,5], n = 2
//        输出：[1,2,3,5]
//        示例 2：
//        输入：head = [1], n = 1
//        输出：[]
//        示例 3：
//        输入：head = [1,2], n = 1
//        输出：[1]
public class leetcode_19 {
    //双指针
//    使用双指针思路，注意要创建一个头结点myHead，让myHead.next = head，这样可以成功删掉第一个节点。
//    定义一个慢指针x和快指针y，由于要删除倒数第n个节点，那么我们要找出倒数第n个节点的前驱节点，
//    即倒数第n+1个节点。那么我们先让快指针走n+1步，然后两个指针同时向前走，等快指针走到null的时候，
//    慢指针所指的节点就是倒数第n+1个节点。
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //定义头结点
        ListNode myHead = new ListNode();
        //令myHead.next = head
        myHead.next = head;
        //将两个指针初始化，都指向myHead
        ListNode x = myHead;
        ListNode y = myHead;
        //让快指针先走n+1步
        for(int i = 0; i < n + 1; i++){
            y = y.next;
        }
        //两个指针同时向前走，直到快指针指向null
        while(y != null){
            x = x.next;
            y = y.next;
        }
        //删除倒数第n个节点
        x.next = x.next.next;
        return myHead.next;
    }
    public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }

        public ListNode() {

        }
    }
}
